DSA: Recursion

    In Programming, we have a concept that is super important when we deal with the implementation of trees and graph data structure and it is called recursion. Recursion is a technique offered by many programming languages in which a user-defined function can call itself again and again until a base condition gets satisfied. If a user-defined function calls another user-defined function then it is called indirect recursion. A function is called a recursion function only if it calls itself. A recursive function acts like an iterative statement such as for loop, but using a recursive function can require more memory than an iterative statement and implementing a recursive statement is complex than an iterative one.

    The syntax for Recursion: 

    def function(arg):
    #some statement
    #base condiition
    function()

    Recursion Example in python: 

    def print_n_to_1(n):
    if n==1:
        print(1) # base condition
    else:
        print(n)
        print_n_to_1(n-1)

print_n_to_1(10)

    Output: 

    10
9
8
7
6
5
4
3
2
1

    Properties of a Recursion Function

    While creating a recursion function, we should take care of some recursive properties, or else we could get stuck in the infinite recursive call, which is similar to an infinite loop. So, while writing a recursive statement, make sure your function must have these two properties.

    • Base condition
    • Progressive approach.

    Base Condition

    The recursive function must have a Base condition that returns a single value or terminate the function, rather than calling the function again and again. In the above example, we have provided a base condition that executes if n==1: and it terminates the function and stops the recursive call. If we did not provide a base condition in the above example, the recursive call would get an infinite approach.

    Example:

    Recursion with the base condition Recursion without base condition 
    def print_n_to_1(n):
    if n==1:
        print(1) # base condition
    else:
        print(n)
        print_n_to_1(n-1)

print_n_to_1(10)
    		 
    def print_n_to_1(n):
    print(n)
    print_n_to_1(n-1)

print_n_to_1(10)
    Output 
    10
9
8
7
6
5
4
3
2
1
    		 
    10
9
8
7
6
5
4
3
2
1
0
-1
…
………

    Progressive approach

    The recursive call should be written in such manner, so for each recursive call, we get closer to the base condition. In the above example when we are performing the recursive call, we calling the print_n_to_1(n-1) statement which decrementing the value of n for each recursive call. If we do not perform a Progressive approach in a recursive function we could get stuck in an infinite recursive call. Example:

    Recursion with Progressive approach Recursion without Progressive approach 
    def print_n_to_1(n):
    if n==1:
        print(1) # base condition
    else:
        print(n)
        print_n_to_1(n-1) # With progressive approch

print_n_to_1(10)
    		 
    def print_n_to_1(n):
    if n==1:
        print(1) # base condition
    else:
        print(n)
        print_n_to_1(n) #without progressive approach.

print_n_to_1(10)_1(10)
    Output 
    10
9
8
7
6
5 
4
3
2
1
    		 
    10
10
10
10
10
10
10
…
………

    Recursion Implementation

    Mostly all programming languages use a stack to implement the recursive calling. In general, when a function A calls function B, the control of execution transfer from A to B , the function A get on hold and the execution of function B get started. Once the function B gets completely executed the control of execution goes back to the function A and the execution resume where it was in the hold.

    Example: 

    Normal Function calling:

function A(n):
    B(n++) # go to function B()
    # do something

function B(x):
    #do something with x once done get back to A()

A(n) ------Pause A(n++)------> B(n++) --------Resume A(n++)------> A(n++)

    The same criteria apply for the recursive functions, but here instead of transferring execution control from function A to B, the execution control transfer from function A to function A with different data set.

    For example: 

    function A(n):
      A(n++) # call function A() with n++ argument

A(n) ----------pause A(n)----->A(n++) ----------pause A(n++)----->A(n++++)

    Why use Recursion

    This is a valid question, we have iterators such as loops, for repetitive statements so why use Recursion? The answer is simple. Recursive provides a more readable and simple way to write code, in tree traversal iterators such as for loop are not that much efficient that’s why we use recursive statements over iterators.

    Advantages and Disadvantages of Recursion

    Advantages

    • It provides a simple and clean way to write code.
    • In tree and graph data structure operations such as traversal, insertion, deletion and searching, it is very efficient.

    Disadvantages

    • It takes more space as compared to iterative statements.
    • The time complexity is also higher for many cases.

    People are also reading:

    Previous Tutorial Next Tutorial